In many cases, video data exists using an immense amount of data. Accordingly, when video data is transmitted from a transmission device to a reception device or when video data is stored in a storage unit, that video data receives compression coding.
As representative video coding standards, Moving Picture Experts Group phase 2 (MPEG-2), MPEG-4 or MPEG-4 Advanced Video Coding (MPEG-4 AVC/H.264) are known. These video coding standards are developed by International Organization for Standardization/International Electrotechnical Commission (ISO/IEC).
Also, as a new video coding standard, High Efficiency Video Coding (HEVC, MPEG-H/H.265) is being developed (see non patent document 1 for example).
The above video coding standards adopt two coding methods, i.e., the inter prediction coding and the intra prediction coding. The inter prediction coding is a coding method that uses information of a coded picture in order to code a coding target picture, while the intra prediction coding is a coding method that uses only information included in the coding target picture in order to code the coding target picture.
Videos that are subjects of these video coding standards are natural images, which are obtained mainly by using various types of cameras. However, accompanying the progress in the information technology for consumers in recent years, a trend has emerged in which video coding is applied to screen content images such as those displayed in a personal computer (PC) desk top etc. in addition to the application of video coding to natural images.
As a specific example of video coding of screen content images, there is a wireless display, which wirelessly transmits images displayed on a PC or a game device to a flat panel display device. As another specific example, there is Virtual Display Infrastructure (VDI), which transmits a user window of a virtual operating system to a mobile device using the Internet protocol.
Screen content images are artificial images generated by using computer graphics etc., and have characteristics different from those of natural images. The first characteristic of screen content images is low correlation of pixels. In natural images, the correlation is high between the pixel value of a target pixel and the pixel value of an adjoining pixel. Discrete Cosine Transform (DCT) adopted by all video coding standards utilizes this high correlation, and can realize high compression efficiency.
By contrast, a screen content image has many regions in which the correlation of pixel values is low. Examples of this include the boundary portions between the foreground and the background in an animation screen, the outlines of characters in PC window, and others. When DCT is applied to these regions, distortions of high-frequency components called mosquito distortions are perceived visually and remarkably particularly under a condition with a low bitrate.
The second characteristic of screen content images is repeating of the same pattern. A display window of text editing software executed by a PC for example displays many same characters.
The third characteristic of screen content images is a poor variation of pixel values. In an example of text editing software, the display window is often configured of a uniform background color (such as a white color) and character fonts using a limited color such as a black color etc. An RGB 24-bit natural image allows RGB combinations of 2^(8*3) colors (=16,777,216 colors), while a screen contents image often limits the number of RGB combinations to several tens of colors at most.
In the first version of the HEVC, which was internationally standardized in 2013, a technique of conducting highly-efficient compression coding on screen content images is introduced partially. A specific example among others is Transform Skip (TS), which skips DCT applied for prediction errors in the intra prediction coding and the inter prediction coding.
Further, in the next version of HEVC, which is being standardized, a technique of increasing further the compression efficiency of screen content images is about to be introduced (see non patent document 2 for example). Specific examples include the intra block copy that is suitable for the second characteristic of a screen contents image and the palette coding that is suitable for the third characteristic of a screen contents image.
The intra block copy is a coding scheme that introduces the concept of the inter prediction coding to the intra prediction coding. In the intra block copy, the displacement between a process block, which is a coding target, and an area having a pixel value close to those of the process block is coded. This displacement is information corresponding to motion vectors in the inter prediction coding.
Next, before explaining the palette coding, explanations will be given to the poorness of the variation of pixel values, which is the third characteristic of screen content images.
FIG. 1 illustrates a distribution of pixel values in a case when a black character “i” is displayed on the white background in a desktop window of a PC as an example of a screen content image. In order to explain the distribution of the pixel values by using gray scale images instead of color images, FIG. 1 through FIG. 3 use images obtained by converting RGB 24-bit color images into gray scale images and performing dithering on the resultant images.
The pixel values in an image 101 in the rectangular area containing character “i” displayed in the display window of the PC are for white colors for the background and black colors for the foreground, which account for only a small part of the 16,777,216 colors that can emerge in natural images.
An image 102 is a result of enlarging the image 101 so that each pixel can be identified. When a character is displayed on a display window of a PC, an anti-aliasing process is often applied so that the outline of the character looks smooth. Due to the anti-aliasing process, colors other than white or black colors emerge around character “i”. Still, the number of the emerging colors is limited, and is only five in the example illustrated in FIG. 1.
A palette 103 represents the variation of the pixel values included in the image 102 and includes a list of pairs of indexes and RGB values. Each entry in the palette 103 includes an index and an RGB value, and an RGB value includes the pixel values of R, G and B. An index is identification information for colors, and is referred to as a color number. A variation of pixel values described by a palette is also referred to as palette information.
Palette coding is a technique that utilizes the above smallness in the number of colors in images so as to achieve compression efficiency higher than that of DCT. Specifically, a palette is first used so as to replace the pixel value of each pixel in a process block as a coding target with the corresponding index in the palette. Next, a plurality of indexes are converted into one-dimensional data through a coding scheme such as Differential Pulse Code Modulation (DPCM) etc. Then, the encoded indexes and the palette information receive entropy coding. Palette coding can realize high compression efficiency for screen content images.
FIG. 2 illustrates an example of palette coding. When the image 102 illustrated in FIG. 1 is an image of a process block, a palette 103 is generated from each pixel value of the image 102. Next, by replacing each pixel value of the image 102 with an index by using the palette 103, an index image 201 is generated. Thereafter, the index image 201 is coded by DPCM etc., and a coded image is generated.
A technique of improving the Base Color and Index Map (BCIM) mode for coding screen content images is also known (see non patent document 3 for example). Prediction coding of palette information based on a template is also known (see non patent document 4 for example). Prediction coding of palette information based on an adjoining block is also known (see non patent document 5 for example). Modification of the palette mode of non patent document 5 is also proposed (see non patent document 6 for example).
An image compression device is also known that can improve, without deteriorating the image quality, the compression rate even for image data, of multiple values, that is expressed in a color palette scheme (see patent document 1 for example). An efficient image compression device having scalability for an image of multiple values is also known (see patent document 2 for example).
An image process system is also known that can display more colors than the number of colors in the color palette of a computer terminal or a mobile terminal that is to be accessed. An image coding device is also known that determines a threshold for determining whether to conduct pelletization in accordance with the block size of the unit of coding, and thereby improves the coding efficiency.    Patent document 1: Japanese Laid-open Patent Publication No. 2002-142119    Patent document 2: Japanese Laid-open Patent Publication No. 2003-134532    Patent document 3: Japanese Laid-open Patent Publication No. 2007-312152 (Japanese Patent No. 3944524)    Patent document 4: Japanese Laid-open Patent Publication No. 2008-311792    Non patent document 1: ITU-T H.265| ISO/IEC 23008-2, “High efficiency video coding”, 2013    Non patent document 2: D. Flynn et al., “High Efficiency Video Coding (HEVC) Range Extensions text specification: Draft 6”, JCTVC-P1005, 16th JCT-VC Meeting, San Jose, US, 9-17 Jan. 2014    Non patent document 3: C. Lan, J. Xu, G. J. Sullivan, F. Wu, “Improvements of the BCIM mode for screen content coding”, JCTVC-F200, 6th JCT-VC Meeting, Torino, I T, 14-22 July, 2011    Non patent document 4: W. Zhu, H. Yang, “Template-based palette prediction”, JCTVC-N0169, 13th JCT-VC Meeting, Incheon, K R, 18-26 Apr. 2013    Non patent document 5: L. Guo, M. Karczewicz, J. Sole, “RCE3: Results of Test 3.1 on Palette Mode for Screen Content Coding”, JCTVC-N0247, 14th JCT-VC Meeting, Vienna, AT, 25 July-2 Aug. 2013    Non patent document 6: L. Guo, M. Karczewicz, J. Sole, R. Joshi, “Non-RCE3: Modified Palette Mode for Screen Content Coding”, JCTVC-N0249, 14th JCT-VC Meeting, Vienna, AT, 25 July-2 Aug. 2013